# #1.斐波那契
# #编写斐波那契数列的函数并调⽤
# def fib(n):##n是形参
#     a,b =1,1
#     while a<n:
#         print(a,end=' ')
#         a,b = b,a+b
#         print(a,b)
# fib(1000)
# #2.使⽤递归法对整数进⾏因式分解
# from random import randint
# def factors(num, fac=None):
#     if fac is None:
#          fac = []
#     for i in range(2, int(num**0.5)+1):
#         if num%i == 0:
#             fac.append(i)
#             factors(num//i, fac)
#             break
#     else:
#         fac.append(num)
#     return fac
# n = randint(2, 10**8)
# facs = factors(n)
# result = '*'.join(map(str, facs))
# if n == eval(result):
#     print(n, '= '+result)
import copy
from itertools import cycle

from sklearn.datasets import load_sample_image


# #3.编写并使⽤能够⽣成斐波那契数列的⽣成器函数
# def f():
#     a, b = 1, 1 #序列解包，同时为多个元素赋值
#     while True:
#         yield a #暂停执⾏，需要时再产⽣⼀个新元素
#         a, b = b, a+b #序列解包，继续⽣成新元素
# a = f() #创建⽣成器对象
# for i in range(10): #斐波那契数列中前10个元素
#     print(next(a), end=' ')
# #4.编写函数，接收字符串参数，返回⼀个元组，其中第⼀个元素为⼤写字⺟个数，第⼆个元素为⼩写字⺟个数
# def demo(s):
#     result = [0, 0]
#     for ch in s:
#         if ch.islower():
#             result[1] += 1
#         elif ch.isupper():
#             result[0] += 1
#     return tuple(result)
# print(demo('1232sadasdsaASASAS'))
# #5.编写函数，接收⼀个整数t为参数，打印杨辉三⻆前t⾏
# def yanghui(t):
#     print([1])
#     line = [1, 1]
#     print(line)
#     for i in range(3, t+1):
#         r = []  #用来接受中间值的
#         for j in range(0, len(line)-1):
#             r.append(line[j]+line[j+1])
#         line = [1]+r+[1]
#         print(line)
# yanghui(5)
# # [1]             # 第1行
# # [1, 1]          # 第2行
# # [1, 2, 1]       # 第3行
# # [1, 3, 3, 1]    # 第4行
# # [1, 4, 6, 4, 1] # 第5行

# #6.编写函数，接收⼀个正偶数为参数，输出两个素数，并且这两个素数之和等于原来的正偶数。如果存在多组符合条件的素数，则全部输出。
# def demo(n):
#     def IsPrime(p):
#         if p == 2:
#             return True
#         if p%2 == 0:
#             return False
#         for i in range(3, int(p**0.5)+1, 2):
#             if p%i==0:
#                  return False
#         return True
#     if isinstance(n, int) and n>0 and n%2==0:#输入一个正偶数
#          for i in range(2, n//2+1):
#             if IsPrime(i) and IsPrime(n-i):
#                 print(i, '+', n-i, '=', n)
# demo(12)
# #7.编写函数，计算字符串匹配的准确率。 以打字练习程序为例，假设origin为原始内容，userInput为⽤⼾输⼊的内容，下⾯的代码⽤来测试⽤⼾输⼊的准确率。
# def rate(origin, userInput):
#     if not (isinstance(origin, str) and isinstance(userInput, str)):
#         print('The two parameters must be strings.')
#     return
#     right = sum((1 for o, u in zip(origin, userInput) if o==u))
#     return round(right/len(origin), 2)
# print(rate('aabbc','aabbb'))

# #8.编写函数模拟猜数游戏。系统随机产⽣⼀个数，玩家最多可以猜5次，系统会根据玩家的猜测进⾏提⽰，玩家则可以根据系统的提⽰对下⼀次的猜测进⾏适当调整。
# from random import randint
# def guess(max=100, times=5):
# #随机⽣成⼀个整数
#     value = randint(1,max)
#     for i in range(times):
#          if i == 0:
#              prompt = 'Start to GUESS:'
#          else:
#              prompt = 'GUESS Again:'
#              #使⽤异常处理结构，防⽌输⼊不是数字的情况
#          try:
#             x = int(input(prompt))
#          except:
#             print('Must input an integer between 1 and ', max)
#          #猜对了
#          else:
#              if x == value:
#                      print('Congratulations!')
#                      break
#              elif x > value:
#                      print('Too big')
#              else:
#                      print('Too little')
#     else:
#         #次数⽤完还没猜对，游戏结束，提⽰正确答案
#         print('Game over. FAIL.')
#         print('The value is ', value)
# guess(10)

# #9.编写函数模拟报数游戏。有n个⼈围成⼀圈，顺序编号，从第⼀个⼈开始从1到k（假设k=3）报数，报到k的⼈退出圈⼦，然后圈⼦缩⼩，从下⼀个⼈继续游戏，问最后留下的是原来的第⼏号。
# def demo(lst, k):
#        #切⽚，以免影响原来的数据
#        t_lst = lst[:]
#        #浅拷贝
#        # t_lst = copy.copy(lst)
#        # t_lst = list(lst)
#        #深拷贝
#        #t_lst = copy.deepcopy(lst)
#        # 游戏⼀直进⾏到只剩下最后⼀个⼈
#        while len(t_lst) > 1:
#            # 创建cycle对象
#            c = cycle(t_lst)
#            # 从1到k报数
#            for i in range(k):
#                t = next(c)
#            # ⼀个⼈出局，圈⼦缩⼩
#            index = t_lst.index(t)
#            t_lst = t_lst[index + 1:] + t_lst[:index]
#            # 游戏结束
#        return t_lst[0]
# lst = list(range(1,11))
# print(demo(lst, 3))


# #汉诺塔问题基于递归算法的实现。
# def hannoi(num, src, dst, temp=None):
#     #声明⽤来记录移动次数的变量为全局变量
#     global times
#     #确认参数类型和范围
#     assert type(num) == int
#     assert num > 0
#     #只剩最后或只有⼀个盘⼦需要移动，这也是函数递归调⽤的结束条件
#     if num == 1:
#          print('The {0} Times move:{1}==>{2}'.format(times, src, dst))
#          times += 1
#     else:
#         #递归调⽤函数⾃⾝，
#         #先把除最后⼀个盘⼦之外的所有盘⼦移动到临时柱⼦上
#         hannoi(num-1, src, temp, dst)
#         #把最后⼀个盘⼦直接移动到⽬标柱⼦上
#         hannoi(1, src, dst)
#         #把除最后⼀个盘⼦之外的其他盘⼦从临时柱⼦上移动到⽬标柱⼦上
#         hannoi(num-1, temp, dst, src)
# #⽤来记录移动次数的变量
# times = 1
# #A表⽰最初放置盘⼦的柱⼦，C是⽬标柱⼦，B是临时柱⼦
# hannoi(3, 'A', 'C', 'B')

# #编写函数计算任意位数的⿊洞数。⿊洞数是指这样的整数：由这个数字每位上的数字组成的最⼤数减去每位数字组成的最⼩数仍然得到这个数⾃⾝。例如3位⿊洞数是495，因为954-459=495，4位数字是6174，因为7641-1467=6174。
# def main(n):
#     '''参数n表⽰数字的位数，例如n=3时返回495，n=4时返回6174'''
#     #待测试数范围的起点和结束值
#     start = 10**(n-1)
#     end = 10**n
#     #依次测试每个数
#     for i in range(start, end):
#     #由这⼏个数字组成的最⼤数和最⼩数
#         little = ''.join(sorted(str(i)))
#         #big = ''.join(reversed(little))
#         big = little[::-1]
#         if int(big)-int(little) == i:
#              print(i)
# n = 3
# main(n)


#编写函数，使⽤算法实现冒泡排序算法。
#654321

# def sort(list1):
#     l = len(list1)
#     for i in range(1,l):
#         for j in range(1,l-i+1):
#             if list1[l - j] < list1[l - j -1]:
#                 list1[l - j] , list1[l - j -1] = list1[l - j -1] , list1[l - j]
#     return list1
#
# list2 = [10,9,6,5,3]
# print(sort(list2))

# #编写函数，模拟选择法排序
# def opt_sort(list1):
#     l = len(list1)
#     for i in range(0,l-1):
#         min_index = i
#         for j in range(i+1,l):
#             if list1[min_index] > list1[j]:
#                 min_index = j
#         list1[min_index],list1[i] = list1[i],list1[min_index]
#     return list1
# print(opt_sort([10,9,8,7,6,5,4]))


#1.2.3.4.5.6.7.8.9


# #编写函数，模拟⼆分法查找
# def half_find(list,x):
#     l = 0
#     r  = len(list) - 1
#     while True:
#         mid = (l + r) // 2
#         if  x == list[mid]:
#             return mid
#         elif x > list[mid]:
#             l = mid + 1
#         elif x < list[mid]:
#             r = mid - 1
# print(half_find([1,2,3,4,5,6],5))


# #编写函数，查找给定序列的最⻓递增⼦序列。
# from itertools import combinations
# from random import sample
# def subAscendingList(lst):
#     '''返回最⻓递增⼦序列'''
#     for length in range(len(lst), 0, -1):
#             #按⻓度递减的顺序进⾏查找和判断
#          for sub in combinations(lst, length):
#              #判断当前选择的⼦序列是否为递增顺序
#              if list(sub) == sorted(sub):
#                 #找到第⼀个就返回
#                 return sub
# def getList(start=0, end=1000, number=20):
#     '''⽣成随机序列'''
#     if number > end-start:
#          return None
#     return sample(range(start, end), number)
# def main():
#          #⽣成⼀个包含10个随机数的列表进⾏测试
#          lst = getList(number=10)
#          if lst:
#             print(lst)
#             print(subAscendingList(lst))
# main()
